package simple;

/**
 * 18:29 ~ 18:43 (14分钟)
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * 链接：https://leetcode-cn.com/problems/search-insert-position
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class SearchInsertPosition {
    /**
     * 显而易见，使用二分查找法。
     * 难点在于 为什么while循环中是<= 而不是 <
     * */
    class Solution {
        public int searchInsert(int[] nums, int target) {
            if(nums.length == 0){
                return 0;
            }
            int left = 0;
            int right = nums.length-1;

            while(left <= right){
                int mid = (left + right) / 2;
                if(target == nums[mid]){
                    return mid;
                }
                if(target < nums[mid]){
                    right = mid-1;
                }
                else{
                    left = mid+1;
                }
            }
            return left;
        }
    }
}
